
\chapter{铁路票额预分优化模型与算法}

本章的主要工作是运用第二章提出的建模框架优化票额预分方案。目前，我国铁路客运营销的一线管理人员在制订票额预分方案的工作当中，采用了一套高效、直观的术语体系来描述票额预分相关概念（如之前介绍的固定票额分配，席位裂解、共用和复用等）。这套术语体系简单高效同时也非常直观的反映了铁路客票销售的业务流程。有很多研究是直接采用这一套语言进行建模分析，如文献\parencite{赵翔赵鹏-168,史峰陈彦-125,骆泳吉刘军-165}。然而，这套术语与我国客票系统的实现结合过于紧密，不利于构造数学模型。为应用第二章提出的建模框架，首先要用收益管理的术语（存量单位、产品等）对票额预分的相关概念重新定义。

\section{票额预分}

根据第一章的介绍，票额预分机制是通过将席位放入三种不同类型的分组中实现的（共用分组，通用分组和通售分组）\footnote{为便于表达，本文在翻译时将这三种分组分别记为Type I，Type II 和 Type III}。从收益管理的角度上来看，票额预分其实是一个综合了分割式和嵌套式上限控制模式的复合客票销售规则。除此之外，票额预分对每列车的控制是独立的，即每列车有一个单独的票额预分方案。下面由易到难逐个以收益管理的语言重新定义票额预分涉及的三类分组。

通售分组最为简单，它实现的是``先到先得'' (First-Come-First-Serve)的控制模式，即只要有足够的存量单位，它可以出售所有的产品。一列车只有一个通售分组。通售分组中可以放入任意的存量单位，在客票销售时只要通过席位分配规则能找到合适的存量单位，就可以售出车票。

通用分组实现的是分割式上限控制模式，即在通用分组中存放的是已经组合好的车票。一个通用分组的示例如例1-2所示。一列车可以有多个通用分组，每个分组被分配了一定量的存量单位且只能出售一种产品。所以，一个通用分组可以用其出售的产品标识。需要注意的是，一个特定类型的通用分组需要的存量单位是指定的，如例1-2中的A-C通用分组只能支持放入列车区段A-B和B-C的对应的存量单位。

票额预分中最复杂的机制是共用分组，它实现的是灵活的上限控制。一个共用分组包含了两部分内容：它所能出售的产品和分配给它的存量单位。共用分组的存量单位是以席位为单位分配的，一个座位所对应的所有存量单位会被同时分配给一个共用分组。一列车可以有多个共用分组。下面结合一个例子解释共用分组的表达。

\textbf{例3-1. 一列车的共用分组}

如图\ref{fig:1-5}所示，对一列从A站出发到I站的列车，设置了两个共用分组。分组1中放置了座位1-3的全部存量单位，它可以出售的产品是A-F,
A-G, A-H 和 A-I(从A站卖到F站以远)。分组2中放置了座位4-5的全部存量单位，它可以出售的产品是B-G, B-H, B-I,
C-G, C-H和C-I(从B-C区间卖到G站以远)。

\begin{figure}[htb]
\centering \includegraphics[bb = 0 0 200 100, draft, type=eps]{LyX/Fig_1-5.png}
\bicaption[fig:1-5]{例3-1中的共用分组设置}{例3-1中的共用分组设置}{Fig}{The
settings of type I buckets in Example 3-1} 
\end{figure}

共用分组中可售产品集合是通过指定限售站和以远站决定的。需要注意的是，一个共用分组的所有可售产品需要满足以下两个条件：1）始发站必须是从同一个车站或者遍布某一个区间(出发区间)；2）终到站必须是从某一个车站或遍布某一个区间（到达区间）。在例3-1中，一个可行的共用分组的产品集合图\ref{fig:1-6}所示。该分组中共用站是B，其票额可以被C、D站使用，售票的以远站为F，限售站没有设置所以默认为车站I。

\begin{figure}[htb]
\centering \includegraphics[width=0.7\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_1-6.png}
\bicaption[fig:1-6]{一个可行的共用分组示例}{一个可行的共用分组示例}{Fig}{A feasible
product set of type I bucket} 
\end{figure}

席位复用同样可以解释为对存量单位的使用规则。在从共用分组中售出一张车票后，如果不是正好从第一站到最后一站的车票，会有存量单位剩余。剩余的存量单位将会通过复用机制进入通用或者通售分组中。图\ref{fig:1-7}中展示了从例3-1中的分组2中出售一张B-H的车票后，剩余的存量单位向通用分组复用的过程。除此之外，复用出的席位也可以加入“先到先服务”机制的通售分组。

\begin{figure}[htb]
\centering \includegraphics[bb = 0 0 200 100, draft, type=eps]{LyX/Fig_1-7.png}
\bicaption[fig:1-7]{席位复用示例}{席位复用示例}{Fig}{An example of reusing
SKU} 
\end{figure}

如果一种产品可以同时从这三种分组中售出，它们的售票优先级一般是通售分组 \textgreater 通用分组\textgreater
共用分组，即在同时都能出售某种产品时，优先从通售分组售出，其次是通用分组，再次是共用分组。在预售期开始时，铁路客运营销人员会向共用分组，通用分组和通售分组中分配存量单位，并且设置具体的复用规则。

通过以上对票额预分的机制的重新定义，票额预分优化问题可以理解在预售期开始之前做出以下决策：

(1) 共用分组的可售产品集合，即每个共用分组的出发（站）区间和到达站（区间）； (2) 共用分组的复用规则； (3) 每个分组中分配存量单位的数量。

为了简化问题，本章做出以下假设:1)仅向共用分组分配票额的情况，2)仅向通用分组复用的方式，3）不考虑限售站，即限售站默认设置为列车的终点站。事实上，通用分组可以看作是仅有一个出发和到达车站的一类特殊的共用分组。所以在以下建模过程中，通用分组不被直接分配票额（但是可以通过复用产生）。另外，由于我国铁路售票系统的限制，本文仅考虑至多有5个共用分组的情况。

\section{问题建模}

本章的研究基于我国铁路客票销售组织现状，它主要有两方面特点：1）基于里程定价，车票的价格随着乘坐列车的里程的增加而增加；2）车票价格在预售期内固定，同一车次同一座席类别（一等座、二等座）的车票价格在售票过程中不发生改变。

在用收益管理的语言重新定义票额预分机制后，就可以通过第二章提出的建模框架对问题进行建模和求解了。首先需要做的是将票额预分用模型语言表达，填充模型的细节部分。下面就按建模框架的组成部分逐一介绍。为表述方便，本章内用$I$表示列车的集合，用$i\in I$
索引。列车$i$的所有席位用$c_{i}$表示。同第二章，令$J$表示产品集合, 用$j\in J$索引。令$B_{i}$表示列车$i$的所有共用分组的集合，用$b\in B_{i}$索引。所有的共用分组的集合用$B$表示，有${B_{i}}\subset B,\forall i\in I$。

本章采用的符号列表如表\ref{tab:3-1}所示。

\begin{table}[!hpb]
\centering \bicaption[tab:3-1]{符号列表}{符号列表}{Table}{Symbol
list} %
\begin{tabular}{ll}
\hline 
集合  & \tabularnewline
\hline 
$T$  & 预售期长度，通过 $t=1,\ldots,T$索引 \tabularnewline
$I$  & 列车集合，通过 $i$ 索引\tabularnewline
$J$  & 产品集合，通过 $j$ 索引 \tabularnewline
$L$  & 所有细分市场的集合，通过 $l$ 索引\tabularnewline
$J_{l}$  & 细分市场 $l$ 的所有可行路径，其中 $l\in L$ \tabularnewline
$B$  & 共用分组的集合，通过 $b$ 索引 \tabularnewline
\hline 
随机变量  & \tabularnewline
\hline 
$X_{t}$  & 在时间段 $t$ 共用分组剩余的席位 \tabularnewline
$Q_{t}$  & 在时间段 $t$ 通用分组剩余的产品数量 \tabularnewline
$U_{t}$  & 产品在时间段 $t$ 的开放情况 \tabularnewline
\hline 
向量  & \tabularnewline
\hline 
$\boldsymbol{y}$  & 0-1变量，表示产品与共用分组的关联（决策变量） \tabularnewline
$\boldsymbol{z}$  & 初始的席位分配数量（决策变量） \tabularnewline
\hline 
参数  & \tabularnewline
\hline 
$\delta_{j,h}$  & 复用关系0-1向量。如果产品 $j$ 可以通过在产品$h$销售\tabularnewline
 & 之后复用出来，它取值为1，否则等于0\tabularnewline
$r_{j}$  & 产品 $j$ 的价格 \tabularnewline
$c_{i}$  & 列车 $i$ 的席位总量 \tabularnewline
${\beta_{j}^{l}}$  & 细分市场 $l$ 对产品 $j$ 的偏好 \tabularnewline
${\rho_{t}}$  & 在时间段 $t$ 有旅客到达的概率 \tabularnewline
$\lambda_{t,l}$  & 在时间段 $t$ 到达的旅客属于细分市场 $l$ 的概率 \tabularnewline
${P'_{j}}\left(\boldsymbol{u}_{t}\right)$  & 产品 $j$ 在时间段 $t$ 和产品开放情况为 $\boldsymbol{u}_{t}$ 的条件下被售出的概率 \tabularnewline
\hline 
\end{tabular}
\end{table}


\subsection{客票销售决策模型}

由于票额预分仅在预售期开始之前对席位进行预分配，所以这是一个“$N=1$”型问题，即仅做一次决策的问题。根据第二章的建模框架，这种问题类型的模型为以下形式。

\[
V\left(\boldsymbol{s}\right)=\max_{a}R(\boldsymbol{s},a)
\]

在票额预分的问题中，还需要具体的制定状态$s$和行动$a$的具体意义。相对于第二章直接采用存量单位的使用情况作为状态变量的建模方式，在票额预分这种客票销售规则下可以简化为采用聚合的状态变量。本章采用$x_{b}$表示共用分组$b$中的席位数量，它可以用来表示共用分组管理的存量单位的使用情况。之所以可以这样表达是因为：第一，存量单位是按照席位加入共用分组的；第二，在售出一张车票后，由于席位复用的原因，无论所售车票是否完全使用了一个席位，其剩余部分都会从共用分组中移除。采用聚合的变量表达在不影响模型表达的精准性的同时，减少问题的复杂度。通用分组中不同产品的剩余数量同样可以采用聚合的方式。令$q_{j}$表示通用分组中产品$j$的剩余数量，它可以表示通用分组管理的存量单位使用状况。注意，在模型中并不需要区别通用分组属于哪列车，因为不同列车的通用分组原本就是不相交的。

状态变量可以表示为$\boldsymbol{s}=(\boldsymbol{x},\boldsymbol{q})$。由于本章仅考虑向共用分组中分配票额，初始的状态变量为$\boldsymbol{x}_{0}=\boldsymbol{0}$和$\boldsymbol{q}_{0}=\boldsymbol{0}$，可以理解为还未向分组中增加任何一个存量单位。

根据对问题的简化，票额预分问题需要制定的决策可以由两类变量表示，分别是产品-共用分组关系变量 $\boldsymbol{y}$ 和分组票额
$\boldsymbol{z}$。其中 $y_{b,j}=1$ 表示产品 $j$ 处于分组 $b$ 的可售集合内。根据对共用分组机制的描述，每种产品只能出现在一个共用分组内，这种关系可以通过式(\ref{eq:3-7})表达。另外，$\boldsymbol{y}$
还要满足可行共用分组的要求（同一个共用分组中的产品应该是从始发站或区间到终到站或区间），记为 $\boldsymbol{y}\in Y$。

\begin{equation}
\sum\limits _{j\in J}{y_{b,j}}\le1\;\;\forall b\in B\label{eq:3-7}
\end{equation}

向各个共用分组分配的票额数量$\boldsymbol{z}$受到列车席位数量的限制，可以表达为式(\ref{eq:3-6})，其中$z_{b}$表示向共用分组$b$分配的席位数量，$c_{i}$表示列车$i$的所有席位的数量。

\begin{equation}
\sum\limits _{b\in B_{i}}{z_{b}=c_{i}}\;\;\forall i\in I\label{eq:3-6}
\end{equation}

预分优化问题就是要通过设置$\left(\boldsymbol{y},{\boldsymbol{z}}\right)$的值使得总收入的期望最大，根据以上论述，客票销售决策问题可以写为如下形式：
\begin{flalign}
 & \mathop{\max}\limits _{{\boldsymbol{y}},{\boldsymbol{z}}}{R}\left({{\boldsymbol{x}_{0}},{\boldsymbol{q}_{0}},{\boldsymbol{y}},\boldsymbol{z}}\right)\nonumber \\
 & s.t.\ \ (\text{\ref{eq:3-6}})(\text{\ref{eq:3-7}})\nonumber \\
 & \boldsymbol{y}\in Y\label{eq:3-8}\\
 & z_{b}\in{\mathbb{Z}^{+}}\;\;\forall b\in B\nonumber \\
 & {y_{b,j}}=\left\{ {0,1}\right\} \;\;\forall b\in B,\forall j\in J\nonumber 
\end{flalign}
在以上问题中，收益的期望值函数$R(\cdot)$的形式需要通过售票过程模型来决定。

\subsection{售票过程模型}

根据建模框架，预售期被分为$T$个足够小的时间段，每一个时间段内至多有一个旅客购票。由于客票销售决策模型是单阶段的，为了简化表达，这里省略售票过程模型中代表客票销售阶段的下标$n$。

在时间段 $t$，系统状态可以用随机变量 $(X^{t},Q^{t})$ 表示。与客票销售决策过程模型类似， $X^{t}$
是席位数量向量，其分量 $X_{b}^{t}$ 表示共用分组 $b$ 在时间段 $t$ 开始时的剩余席位数量。$Q^{t}$
表示通用分组产品数量向量，其中 $Q_{j}^{t}$ 表示产品 $j$ 在时间段 $t$ 开始时的可售数量。

在时间段 $t$ 开始时产品的可售与否用一个0-1向量 $U^{t}$ 表示，其中分量 $U_{j}^{t}=1$ 表示产品
$j$ 在时间段 $t$ 开始时可售。 $U^{t}$ 由式(\ref{eq:3-1})决定。换言之，$U^{t}$ 是状态变量
$X^{t},Q^{t}$ 和决策变量 $\boldsymbol{y}$的一个函数，记作$U^{t}=U(X^{t},Q^{t},\boldsymbol{y})$。其中
$\boldsymbol{y}$ 表示产品-分组关系向量, 其中 $y_{b,j}=1$ 表示产品 $j$ 在分组 $b$
内；$Q_{j}^{t}>0$ 表示产品 $j$ 被通售分组支持； ${\sum\limits _{b\in B}{{X_{b}^{t}}{y_{b,j}}}>0}$
表示产品 $j$ 至少被一个分组支持。 
\begin{equation}
{u_{j}^{t}}=\left\{ {\begin{array}{lc}
1 & {\sum\limits _{b\in B}{{X_{b}^{t}}{y_{b,j}}}>0}\ \text{或}\ Q_{j}^{t}>0\\
0 & \text{其它}
\end{array}}\right.\label{eq:3-1}
\end{equation}

假设只考虑每个旅客只选购一张车票的情况（忽略换乘），对于给定的前一状态，共有$|J|+1$种可能的后续状态。 系统状态转移函数$(X^{t+1},Q^{t+1})=F\left(X^{t},Q^{t},U^{t}\right)$可以显示地通过式(\ref{eq:3-2})和式(\ref{eq:3-3})表示。
\begin{equation}
X_{b}^{t+1}=\left\{ {\begin{array}{lc}
X_{b}^{t}-1 & \text{产品}j\text{在时间段}t\text{内被售出且}Q_{j}^{t}=0\text{ 且 }y_{j}^{b}=1\\
X_{b}^{t} & \text{其它}
\end{array}}\right.\label{eq:3-2}
\end{equation}
\begin{equation}
Q_{j}^{t+1}=\left\{ {\begin{array}{lc}
Q_{j}^{t}-1 & \text{如果产品}j\text{在时间段}t\text{售出且}Q_{j}^{t}>0\\
Q_{j}^{t}+1 & \text{如果产品}h\text{在时间段}t\text{售出且}Q_{h}^{t}=0\text{且}\delta_{j,h}=1\\
Q_{j}^{t} & \text{其它}
\end{array}}\right.\label{eq:3-3}
\end{equation}

\begin{itemize}
\item 令$\delta_{j,h}$表示产品$j$是否可以在产品$h$出售之后被复用出来. 例如，在图\ref{fig:1-7}中，一张A-B的车票和一张H-I的车票可以在售出一张B-H的车票后复用出来，记为$\delta_{A-B,B-H}=1$和$\delta_{H-I,B-H}=1$。 
\item 产品$j$在时间段$t$内被售出的概率与$U^{t}$有关，记为${p_{j}}\left(U^{t}\right)$。那么，在$t$内没有车票售出的概率是$1-\sum\limits _{j\in J}{{p_{j}}\left(U^{t}\right)}$。 
\end{itemize}
为了说明状态转移和在售票期间存量单位的变化情况，这里引入一个例子。假设一列车如图\ref{fig:1-2}所示。从$t=0$开始分别有旅客购买A-D，B-E和D-E的车票。状态变化如图\ref{fig:3-1}所示。

在时间段$t=0$，分组1有4个可用席位，分组2有3个可用席位，记作$X_{1}^{0}=4,X_{2}^{0}=3$. 通售分组为空，记作$Q_{j}^{0}=0,\ \forall j\in J$。

在时间段$t=1$，一张A-D，座位号001的车票从分组1中被售出。通过席位复用，一张D-E的车票被生成出来，加入到通用分组中，记作$X_{1}^{1}=X_{1}^{0}-1=3$
和 $Q_{D-E}^{1}=Q_{D-E}^{0}+1=1$。其它状态变量保持不变。

在时间段$t=2$，一张B-E，座位号006的车票从分组2中被售出。通过席位复用，一张A-B的车票被生成出来，加入到通用分组中，记作$X_{2}^{2}=X_{2}^{1}-1=2$
和 $Q_{A-B}^{2}=Q_{A-B}^{1}+1=1$。其它状态变量保持不变。

在时间段$t=3$，一张D-E，座位号006的车票从通用分组中被售出，记作$Q_{D-E}^{3}=Q_{D-E}^{2}-1=0$。其它状态变量保持不变。

\begin{figure}[htb]
\centering \includegraphics[width=1\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_3-1.png}
\bicaption[fig:3-1]{客票销售过程状态转移示意图}{客票销售过程模型状态转移示意图}{Fig}{An
illustration of the state transition in the ticket reservation process
model} 
\end{figure}

由于产品-价格$j$的售价记为$r_{j}$，它在销售过程中为常量。在时间段$t$内，客票的销售收入记为$R^{t}$，它是一个随机变量，它的分布如式(\ref{eq:3-4})所示。
\begin{equation}
R^{t}=\left\{ {\begin{array}{lc}
r_{j} & \text{如果产品 }j\text{ 在时间段 }t\text{售出}\\
0 & \text{如果时间段}t\text{没有产品售出}
\end{array}}\right.\label{eq:3-4}
\end{equation}

通过构造客票销售模型，目标函数${R}\left({{\boldsymbol{x}_{0}},{\boldsymbol{q}_{0}},{\boldsymbol{y}},\boldsymbol{z}}\right)$的取值等于的$R^{t}$的累加，即式(\ref{eq:3-5})。

\begin{equation}
{R}\left({{\boldsymbol{x}_{0}},{\boldsymbol{q}_{0}},{\boldsymbol{y}},\boldsymbol{z}}\right)={\sum\limits _{t=1}^{T}{R^{t}}\Bigg|X^{0}=\boldsymbol{z},Q^{0}=\boldsymbol{0}}\label{eq:3-5}
\end{equation}

进一步来说，$R^{t}$的取值与时间段$t$内产品$j$售出的概率$P_{j}^{t}(\boldsymbol{u}^{t})$有关，$R^{t}$可以显示的表达为$R^{t}=\mathbb{E}\left\{ \sum_{j\in J}r_{j}P_{j}^{t}(U^{t})\Bigg|X^{0}=\boldsymbol{z},Q^{0}=\boldsymbol{0}\right\} $。其中$P_{j}^{t}(U^{t})$的具体形式取决于旅客行为模型。

\subsection{旅客行为模型}

在对旅客行为的建模上，可以沿用第二章提到的市场细分和旅客选择模型。所有子市场的集合记为$L$，用$l\in L$ 索引。旅客到达过程被建模为泊松流。令${\rho^{t}}$表示在时间段
$t$ 有一位旅客到达的概率。令 $\lambda_{l}^{t}$ 表示在时间段 $t$ 内有一位旅客到达的条件下，这位旅客属于子市场$l$的概率。${P_{j}^{t}}\left({U_{t}}\right)$
可由式(\ref{eq:3-10})计算得到。参数 $(\boldsymbol{\rho},\boldsymbol{\lambda})$
可以由需求预测得到，具体的参数标定过程可以参考第二章。

\begin{equation}
{P_{j}^{t}}\left({U_{t}}\right)={\rho^{t}}\sum\limits _{l\in L}{{\lambda_{l}^{t}}{P'_{l,j}}({U_{t}})}\label{eq:3-10}
\end{equation}

其中，${P'_{l,j}}\left(\boldsymbol{u}\right)$表示一个来自子市场 $l$ 的旅客在产品开放情况
$\boldsymbol{u}$ 下选择产品$j$的概率。对于${P'_{l,j}}\left(\boldsymbol{u}\right)$的具体形式，这里以多项式Logit模型为例，即式(\ref{eq:3-9})。在本章中，这个模型可以被其他类型替代，如文献\parencite{TalluriRyzin-414}提到的混合Logit模型或者是文献\parencite{HosseinalifamMarcotte-628}提到的偏好排序模型。

\begin{equation}
{P'_{l,j}}\left({\boldsymbol{u}}\right)=\frac{{{u_{j}}\beta_{j}^{l}}}{{\sum\limits _{h\in{J_{l}}}{{u_{h}}\beta_{h}^{l}+\beta_{\emptyset}^{l}}}},\ \ \ \forall l\in L\label{eq:3-9}
\end{equation}

\begin{itemize}
\item ${\beta_{j}^{l}}$ 表示产品 $j$ 对于子市场 $l$ 旅客的效用权重，${\beta_{\emptyset}^{l}}$
表示放弃出行的效用权重。 
\item $J_{l}$ 表示子市场 $l$ 旅客的所有可选产品集合。 
\item $u_{j}$ 表示产品$j$开放与否，产品开放时取1，反之取0。 
\end{itemize}

\section{问题求解}

虽然本章的问题中客票销售决策问题是一个单阶段的决策问题，在求解上仍然存在两方面比较大的困难。

首先，虽然在特殊的复用规则下，通过构建售票过程模型和旅客选择模型，目标函数可以有解析形式。但是目标函数值难以直接计算，因为需要遍历每个时间段产品售出的情况，即需要遍历节点数量为
$(|J|+1)^{T}$ 的树形结构，而其中 $|J|$ 和 $T$ 在实际案例中都非常大。一有10个停站的列车会有45个产品，一条繁忙干线每天会有上百列车在上面行驶。$T$
取决于旅客的数量，按照文献\parencite{LeeHersh-476}的方法标定，通常标定百人左右的到达队列需要$T$的取值以万计。遍历如此庞大数量的情况显然难以通过当下的计算水平快速运行。

其次，共用分组内的产品组合通常难以通过分支-定界方法遍历。一方面在本章提出的模型中，可行的共用分组约束 $\boldsymbol{y}\in Y$
难以表达为一个解析形式。另外$y_{b,j}$ 可能的取值组合数是 $2^{|B|\times|J|}$。对于一列有10个停站的列车，这个数字为
$2^{5\times45}$。即使不考虑为分组分配席位的决策变量$\boldsymbol{z}$，遍历求解这个量级的问题也几乎不可能。

综上所述，本章提出的问题难以通过一些现有的商业求解器（如CPLEX和GUROBI）进行求解。为了解决第一个难点，\ref{section3.2.1}节将引入样本平均法(sample
average approximation, SAA)，通过仿真来估测总收入。为了解决第二个难点，在后文的求解中更多的采用了启发式的方法解决问题。

\subsection{样本平均法}

\label{section3.2.1}

为了解决第一个求解难点，即如何评价一个票额预分方案的问题，本章采用样本平均的近似方法。样本平均近似的主要思想是通过产生一些售票过程的列样本路径$\hat{\Omega}^{n}$，通过仿真得到每个样本路径$\hat{\omega}\in\hat{\Omega}^{n}$的收入$\hat{R}\left({\boldsymbol{x}_{0}},{\boldsymbol{q}_{0}},{\boldsymbol{y}},\boldsymbol{z},\hat{\omega}\right)$。最后采用这些样本的均值来近似替代$R\left({\boldsymbol{x}_{0}},{\boldsymbol{q}_{0}},{\boldsymbol{y}},\boldsymbol{z}\right)$，如式(\ref{eq:3-11})所示。

\begin{equation}
R\left({\boldsymbol{x}_{0}},{\boldsymbol{q}_{0}},{\boldsymbol{y}},\boldsymbol{z}\right)\approx\frac{1}{|{\hat{\Omega}}|}\sum_{\hat{\omega}\in{\hat{\Omega}}}\hat{R}\left({\boldsymbol{x}_{0}},{\boldsymbol{q}_{0}},{\boldsymbol{y}},\boldsymbol{z},\hat{\omega}\right)\label{eq:3-11}
\end{equation}

采样和仿真在第二章中有具体解释，这里简单介绍流程，它包含两步： 
\begin{enumerate}
\item 依据需求参数 $(\boldsymbol{\rho},\boldsymbol{\lambda})$ 对旅客进行采样。 
\item 进行旅客购票仿真，计算总收入平均值。 
\end{enumerate}
一个样本是一个旅客到达的序列，包含旅客开始购票的时间和它所从属的子市场。根据之前的假设，旅客的到达是服从泊松分布的。旅客的到达时间可以参考文献\parencite{LeeHersh-476}的方法生成。旅客所从属的子市场可由轮盘法产生。购票过程可以看做一个离散事件仿真系统。本文在实验中采用了进程交互法驱动仿真的进行，其中，每个旅客都有一个事件列表。为了加速仿真的过程，这里引入一些假设：
\begin{itemize}
\item 忽略旅客查询产品信息和支付所消耗的时间。 
\item 忽略售票系统处理购票请求和更新数据所消耗的时间。 
\item 售票系统每次只处理一个查询或者交易的事件。 
\end{itemize}
当一个旅客开始购票，他会向售票系统发送请求当前出售的产品信息。售票系统更新共用分组和通用分组的信息并回应请求。旅客根据产品信息进行选择。如果旅客购买了一个产品，售票系统会出售一张车票；否则，旅客退出购票过程。

\subsection{遗传算法}

\label{section3.2.2}

从本节开始，要解决求解当中的第二个难点。本章中会介绍两种启发式方法求解票额预分优化问题，本节介绍通过遗传算法的框架来求解问题，下一节中会介绍通过基于规则的启发式方法求解问题。遗传算法是受自然选择和遗传启发的一个自适应启发式搜索算法。它包含了以下概念：染色体，基因，适应度以及几种对染色体的操作（算子）：选择、交叉、变异。接下来将按照遗传算法的各个要素介绍如何通过算法的细节。

\subsubsection{编码方式}

\begin{figure}[htb]
\centering \includegraphics[width=1\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_3-2.png}
\bicaption[fig:3-2]{遗传算法中染色体结构示意}{遗传算法中染色体结构示意}{Fig}{The
structure of chromosome in GA} 
\end{figure}

预分优化问题的一个解 $(\boldsymbol{y},\boldsymbol{z})$ 被编码为一个染色体，其中包含若干基因。一个基因内通过很多片段表示共用分组。图\ref{fig:3-2}(a)表示一条染色体，其中每列车包含5个共用分组（对应的，一个基因有5条片段）。一条片段通过5个参数表示一个共用分组：出发区间初始站，出发区间最终站，到达区间初始站，到达区间最终站和分组初始的席位数量。图\ref{fig:3-2}(b)表示一条片段，其中前4个参数定义了一个分组中可售产品的范围，即$\boldsymbol{y}$变量。

通过基因片段的构造设计，可以表达一个共用分组的基本信息。然而，为了保证票额预分方案的可行性，还需要引入以下规则： 
\begin{enumerate}
\item 为了满足约束(\ref{eq:3-8})，需要保证三个条件：1）一个基因片段的车站要保证一定的前后方关系，也就是说出发区间和到达区间的最终站在初始车站之前；2）
到达区间最终站是列车运行的最后一站（不考虑限售）；3）出发区间的最终站在到达区间的初始站之前。 
\item 为了满足约束(\ref{eq:3-6})，基因中所有片段中的席位数量之和等于列车的席位数。 
\item 为了满足约束(\ref{eq:3-7})，每个基因片段的出发区间不能重叠。 
\item 每个基因中，基因片段的数量是固定的（这取决于售票系统支持多少分组数量）。如果出现列车的停站数量小于支持的分组数量时，可以引入虚拟片段（产品集合为空，分配座位数量为0）。 
\end{enumerate}
需要注意的是，由于在票额预分中，每列车独立控制，所以每列车的预分方案的可行性互相没有影响。

\subsubsection{适应度}

染色体的适应度是用来评价一个解的优劣的指标。通常适应度函数可以通过问题的目标函数或者其它近似目标函数来代替。这里采用前一节提到的样本平均法计算染色体适应度。首先需要把染色体还原为问题的一个解，通过编码构造可以保证这些解都是问题的可行解。所以可以在还原后直接带入样本平均法的过程中求得适应度值。需要注意的是，这一步操作涉及到售票仿真，且在求解过程当中会被反复的调用，所以用仿真方法作为适应度评价的前提有一个高效的仿真程序。

\subsubsection{交叉操作}

本文采用均匀交叉规则，子代的基因独立地来自两个父代之一的同一位置的基因，如图\ref{fig:3-3}所示。由于列车之间的票额预分是独立的，而交叉算子是在解之间整列车地交换票额预分方案，所以，如果父带染色体是可行的，那么子代染色体对应的解也是原问题的可行解。

\begin{figure}[htb]
\centering \includegraphics[width=1\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_3-3.png}
\bicaption[fig:3-3]{交叉算子示意图}{交叉算子示意图}{Fig}{illustration
of crossover} 
\end{figure}


\subsubsection{变异操作}

变异操作是通过随机的修改基因上的某一些参数值以探索之前未遍历的解的一种机制。变异操作需要指定变异规则（即如何选择变异的基因）和变异的方向（以何种规则改变参数的值）。

本文采用等概率变异规则，即每个基因具有相同的概率发生变异。如果在计算过程中选择了变异的基因，本文会随机的再次选择其中一条基因片段并按照如下变异方向改变其值。这些随机数都是在求解过程中实时生成的。

所有可能的变异方向一共有4类，列举如下。图\ref{fig:3-4}展示了不同可能变异方向的示意图。需要注意的是，对于任意一个基因（共用分组），不一定每个变异方向都会产生可行解。所以在决定某一基因为变异基因后，需要先剔除不可行的变异方向，再进行变异方向的随机选择。 
\begin{itemize}
\item 向前/后移动出发区间的初始站。如果出发区间初始站为列车的始发站，又或者它是后一个共用分组（这里将所有的共用分组按照出发区间的前后顺序排序，后一个共用分组指的是出发区间的车站在此共用分组之后的一个共用分组）的最后一个始发站正好与在此分组始发站相邻，则不能向后移动；同理，如果出发区间初始站与最终站相邻，则不可向前移动。 
\item 向前/后移动出发区间的最终站。出发区间最终站的移动与出发区间初始站相同，如果出发区间最终站为列车终到站或者与前一共用分组出发区间初始站相邻，则不可向前移动；如果出发区间最终站与初始站相邻，则不能向后移动。 
\item 向前/后移动到达区间初始站。到达区间的初始站主要受到出发区间最终站的限制，如果其与出发区间最终站相邻，则不能向后移动；如果其等于列车终点站，则不能向前移动。 
\item 向下一个基因片段（非虚拟基因片段）转移席位。最后一个共用分组不能再转移席位。需要注意的是，单独靠这条规则其实无法遍历所有可能情况，需要配合种群初始值的设置共同作用。

这些变异的方向可以保证如果迭代足够多的代数，所有的解都会被遍历。另外，虚拟基因片段可以通过在产品集合中增加一个合法的产品变为普通的基因片段。
\end{itemize}
\begin{figure}[htb]
\centering \includegraphics[width=1\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_3-4.png}
\bicaption[fig:3-4]{变异算子示意图}{变异算子示意图}{Fig}{illustration
of mutation} 
\end{figure}


\subsubsection{算法初始化}

遗传算法的初始种群的每一个染色体由以下步骤产生：首先，对于每列车，随机选择$n$个停站，其中$n$小于最大分组数量。第二，对于每个选择的停站生成一个共用分组，其出发取件初始站和最终站都设置为这个车站。第三，随机为每个分组生成到达区间的初始站。最后，将席位全部分配给最后方的共用分组。

另外，还需要设置算法的种群规模和算法的停止条件等，这些需要依据问题的规模决定。

\subsection{基于规则的启发式方法}

本节研究的是一个基于共用分组生成规则的启发式方法。其主要思路是根据一系列规则生成共用分组中可售产品（即决策变量$\boldsymbol{y}$），再通过随机次梯度法确定每个共用分组中的席位数量（即决策变量$\boldsymbol{z}$）。这个方法的设计目的是在短时间内生成一个不错的可行解。该可行解可以作为对决策变量的一个粗略的评价，也可以将这个可行解作为遗传算法的初始可行解。因为采用遗传算法求解问题往往需要经过长时间的迭代，一个好的初始可行解可以加快求解的速度。

\subsubsection{算法流程}

基于规则的启发式方法从一个初始的可行解出发，通过不断的仿真和迭代，不断生成新的解。在每次迭代中，根据上一轮仿真中的客票销售情况，先确定新的解中每个共用分组的产品的可售产品，再确定分组中分配的席位数量。下面就这两个过程进行详细介绍。主要的流程如算法\ref{alg:3-1}所示。

\begin{algorithm}[htb]
\caption{基于规则的启发式方法}
\label{alg:3-1} \begin{algorithmic}[1] \STATE 构造初始可行解 $(\boldsymbol{y}^{0},\boldsymbol{z}^{0})$
\\
 \FOR{$i=0$ to 最大迭代次数} \STATE 售票过程仿真，将当前 $(\boldsymbol{y}^{i},\boldsymbol{z}^{i})$
放入仿真环境中。从仿真结果中统计平均收入作为目标函数值。通过后文的方法计算每个产品的边际收益。 \STATE 使用从仿真中提取的信息更新共用分组的可售产品\\
 \STATE 使用从仿真中提取的信息更新共用分组的分配的席位数\\
 \ENDFOR \STATE 返回$(\boldsymbol{y},\boldsymbol{z})$的值。 \end{algorithmic} 
\end{algorithm}

在这个启发式方法中，最关键的步骤就是从仿真中提取对求解问题有价值的信息，并将其运用在生成共用分组的可售产品和分配的席位数量上。实际上，通过仿真购票过程，不仅仅可以得到收入值，还可以得到其他一些有价值的信息，例如不同细分市场旅客的流失人数，售票结束时存量单位的剩余数量。通过这两部分信息可以知哪一些产品是供不应求或者是供过于求的。在共用分组的可售产品和分配的席位数量的迭代中，一个好的迭代方向就是从供过于求的产品集中的共用分组中拿出席位放到供不应求的产品集中的共用分组中。而在同一个分组内部，应该尽可能的剔除明显的供过于求的产品。为了量化刚才提到的“供不应求”或者“供过于求”的概念，本节引入边际收益作为衡量产品和共用分组价值的指标。下面首先介绍产品和共用分组的边际收益，再介绍通过这两个重要指标生成共用分组的方法。

\subsubsection{计算产品的边际收益}

产品和共用分组的边际收益在本节的定义为：对于产品来说，其边际收益就是如果仅为此产品提供多出售一张票存量资源，最终收入的增加量。对一个共用分组来说，其边际收益就是如果向其中增加一个席位（而不减少其它分组中的席位数量）带来的最终收入的增加量。令${q_{j}}$为产品$j$的边际收入，它的值可以从仿真的结果中通过式(\ref{eq:3-12})计算而来。
\begin{equation}
{q_{j}}={r_{j}}\cdot\left(min\left\{ \bar{N}_{j}^{potential},\bar{N}_{j}^{total\_remained}\right\} -\sum\limits _{b:{y_{b,j}}=1}{N_{b,j}^{bucket\_remained}}\right)\label{eq:3-12}
\end{equation}

\begin{equation}
\bar{N}_{j}^{potential}=\sum\limits _{l}{{P_{l,j}}\left(J\right)}\cdot\bar{N}_{l}^{loss}\label{eq:3-13}
\end{equation}

\begin{itemize}
\item 令 $\bar{N}_{j}^{potential}$ 表示潜在的旅客数量，它通过式(\ref{eq:3-13})计算得来，假设如果有足够的资源还能够增加的旅客数量。 
\item 令 $\bar{N}_{l}^{loss}$ 表示细分市场 $l$ 的损失旅客数量。损失的旅客数量指的是因为无法买到车票而放弃出行的人数。 
\item 令 $\bar{N}_{j}^{total\_remained}$ 表示没有使用的存量单位支持出售产品$j$的平均最大数量。 
\item 令 $N_{b,j}^{bucket\_remained}$ 表示共用分组$b$中没有使用的存量单位支持出售产品$j$的平均最大数量。 
\end{itemize}
通过产品的边际收入计算过程可知，如果可以通过将直到预售期结束都没有出售的一个席位预先的分配给产品$j$使用，那么预期的收入就会增加${q_{j}}$。然而，通过共用分组的策略并不能直接为产品$j$分配存量。所以，还需要在共用分组的角度上考虑多余存量的分配。为了衡量共用分组$b$的供求情况，令${q_{b}}$为共用分组$b$的边际收入衡量指标。在本节提出的方法中，近似地通过该共用分组中所有的可售产品的边际成本之和作为分组的边际收入衡量指标值。通过之前计算的${q_{j}}$的值，利用式(\ref{eq:3-11})近似估测${q_{b}}$。

\begin{equation}
{q_{b}}=\sum\limits _{j\in J:{y_{b,j}}=1}{q_{j}}\label{eq:3-11}
\end{equation}


\subsubsection{计算共用分组的可售产品与席位数量}

在计算对于每列车的每个产品的边际收入之后，分别通过一个启发式规则生成新的共用分组的可售产品和分配席位数量。首先介绍新共用分组可售产品的生成规则。

通过仿真计算，对于一列车所有产品都可以计算出与之相对应的一个边际收入值。制定共用分组可售产品的过程就是要找到平均边际收入最高的产品组合。下面提出一个搜索最优产品组合的方法，其基本思路是先不考虑席位共用，确定被共用车站；然后再根据以其他车站为出发站的产品的边际收入情况考虑共用。具体的流程如下：\\
 (1) 根据始发站将一列车的产品分为不同的分组。相当于不考虑席位共用，每一个车站都被当做被共用车站。\\
 (2) 在每一个车站对应的分组中，按照产品的由长到短的顺序，依次遍历每个产品。如果增加一个产品能够增加该分组的边际收入，则将此产品纳入到分组中；如果加入一个产品会使得该分组的边际收入大幅减少（可以设置一个边际收入的减少阈值，例如本文取50\%），则停止遍历，以此产品的终点站作为以远站。\\
 (3) 选取边际收入最大的5个分组的车站作为被共用车站。\\
 (4) 遍历每个共用车站考虑在保持以远站不变的情况下向前遍历共用车站，直到与下一个共用车站相邻为止。与之前相同，如果增加一个共用车站能够增加该分组的边际收入，则将此产品纳入到分组中；如果加入一个共用会使得该分组的边际收入大幅减少则停止遍历。需要注意的是，如果连续两个共用分组出发区间相邻且以远站相同，则可以合并为一个。

\begin{figure}[htb]
\centering \includegraphics[width=1\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_3-7.png}
\bicaption[fig:3-7]{通过产品的边际收入生成共用分组示意图}{通过产品的边际收入生成共用分组示意图}{Fig}{An
illustration of generating new bucket of type I according to products'
adjustment price} 
\end{figure}

图(\ref{fig:3-7})展示了生成共用分组的可售产品的过程，对于一列从车站A发往车站I的列车，假设产品的边际收入如图(a)所示。通过步骤1、2可以计算得到每个分组的以远站，在图一中用绿底标出。通过对每个分组的边际收入进行计算与排序，如图(b)所示，可得车站A、B、C、D、E可以作为被共用站。由于A、B站分组的以远站相同，它们可以被合并为一个共用分组。依照边际收入的排序，增加F站为被共用车站。共用分组的可售产品最终决策如图(c)所示。

共用分组$b$的席位数量 $x_{b}$ 同样通过分组的边际收入决定。对于边际收入高的分组，应该多分得一些席位。席位数量的确定如式(\ref{eq:3-14})所示。其中
$\left\lfloor \cdot\right\rfloor $ 是向下取整符号。如最后一个分组还有席位剩余则分配给最后方的分组。

\begin{flalign}
{x_{b}}=\left\lfloor {{c^{i}}\cdot\frac{{q_{b}}}{{\sum\limits _{\tilde{b}\in{B^{i}}}{q_{\tilde{b}}}}}}\right\rfloor \forall i\in I\label{eq:3-14}
\end{flalign}


\section{算例}

为了测试本章提出的启发式求解方法的求解效率和解的质量，下面将在两个不同的案例中采用这两种方法。

\subsection{数据准备}

\subsubsection{单列车算例}

第一个算例是基于一个有5个停站(A、B、C、D、E)的列车构成的铁路服务网络。假设列车的席位数量是40个。该列车提供的产品信息如表\ref{table:3-2}所示，每个产品的价格唯一且在售票过程中固定。

\begin{table}[htb]
\centering \bicaption[table:3-2]{产品信息表}{产品信息表}{Table}{Product
information} %
\begin{tabular}{ccccccccccc}
\hline 
产品  & A-B  & A-C  & A-D  & A-E  & B-C  & B-D  & B-E  & C-D  & C-E  & D-E \tabularnewline
\hline 
价格  & 100  & 200  & 300  & 400  & 100  & 200  & 300  & 100  & 200  & 100 \tabularnewline
\hline 
\end{tabular}
\end{table}

此案例中仅采用OD来划分子市场，即每一个OD对应一个子市场。由于本例中只有一列车，每个OD的目标产品就只有一个。需求参数$\boldsymbol{\rho}$
和$\boldsymbol{\lambda}$在预售期内固定，他们的值如表\ref{tab:3-3}所示。

\begin{table}[htb]
\centering \bicaption[tab:3-3]{需求参数}{需求参数}{Table}{Parameters
of demand} %
\begin{tabular}{ccccccccccc}
\hline 
$\rho$  & $\lambda_{A-B}$  & $\lambda_{A-C}$  & $\lambda_{A-D}$  & $\lambda_{A-E}$  & $\lambda_{B-C}$  & $\lambda_{B-D}$  & $\lambda_{B-E}$  & $\lambda_{C-D}$  & $\lambda_{C-E}$  & $\lambda_{D-E}$ \tabularnewline
\hline 
0.20  & 0.025  & 0.05  & 0.075  & 0.063  & 0.025  & 0.15  & 0.175  & 0.2  & 0.225  & 0.025 \tabularnewline
\hline 
\end{tabular}
\end{table}

本案例中在7种不同的需求强度的情景下重复实验。通过调整售票时间长度$T=100,200,300,400,500,600,700$
\footnote{这里的时间长度是相对概念，表示客票销售过程中的时间段数量。}，每个案例中潜在旅客的人数也越来越多。通过这种方式可以考察在需求量从低到高的不同情景下算法的表现。

此案例中样本数量设置为100，票额预分方法通过遗传算法求解，算法参数设定如下： 
\begin{itemize}
\item 最大迭代次数设置为100。 
\item 种群数量设置为100。 
\end{itemize}

\subsubsection{10列车算例}

此案例考虑一个由10列车和5个车站组成的路网，其中每一列车都是站站停列车。案例中涉及旅客的选择数据来源于文献\parencite{HosseinalifamMarcotte-599}(在他们的研究中，每种产品考虑了两种价格，这里仅采用其中的高价格)。旅客对于不同列车的不同产品有着不同的偏好。旅客需求参数$\boldsymbol{\rho}$
和 $\boldsymbol{\lambda}$ 在预售期内为常数。对于每个细分市场，案例设定 $\rho=0.02$ 和 $\lambda=0.1$。
每列车的席位数量设置为50。

本次实验在5组中不同的需求强度下进行了测试。同样需求强度通过参数$T$来控制。这5组实验中$T$的值依次设置为$T=500,2500,5000,10000,15000$。其它设置和单列车相同。

\subsection{结果分析}

单列车算例实验结果如图\ref{fig:3-5}所示，为了与其它客票销售规则比较，在实验中加入了对照组。10列车算例的实验结果如图\ref{fig:3-6}所示。

\begin{figure}[htb]
\centering \includegraphics[width=1\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_3-5.png}
\bicaption[fig:3-5]{单列车算例实验结果}{单列车算例实验结果}{Fig}{The result
of 1-train experiment} 
\end{figure}

\begin{figure}[htb]
\centering \includegraphics[width=1\textwidth,bb = 0 0 200 100, draft, type=eps]{LyX/Fig_3-6.png}
\bicaption[fig:3-6]{10列车算例实验结果}{10列车算例实验结果}{Fig}{The result
of 10-train experiment} 
\end{figure}

为了进一步考虑供需的匹配程度，引入供需指数(load factor)$\gamma$作为衡量指标。供需指数的计算公式可参考文献\parencite{ZhangAdelman-518}。供需指数的数值越高，说明供不应求。通过以上两个实验，可以得到以下结论：

第一，分组的数量并没有显著的影响收入。表\ref{tab:3-4}分析了共用分组的数量对收益的波动（以5个分组为基准）。在单列车案例中情境1，2和4中收益波动较大，而在10列车案例中，波动的幅度在2\%之内。

\begin{table}[H]
\centering \bicaption[tab:3-4]{共用分组数对收入的影响(与5个共用分组相比)}{共用分组数对收入的影响(与5个共用分组相比)}{Table}{The
impact on revenue of changing number of buckets} %
\begin{tabular}{cccccc}
\hline 
\multicolumn{1}{l}{案例} & \multicolumn{1}{l}{情景} & \multicolumn{1}{l}{2个共用分组} & \multicolumn{1}{l}{3个共用分组} & \multicolumn{1}{l}{4个共用分组} & \multicolumn{1}{l}{5个共用分组}\tabularnewline
\hline 
\multirow{7}{*}{单列车案例} & 1  & -1.68\%  & 0.00\%  & -5.88\%  & - \tabularnewline
 & 2  & -7.92\%  & -10.49\%  & -3.22\%  & - \tabularnewline
 & 3  & 1.50\%  & 1.68\%  & -0.04\%  & - \tabularnewline
 & 4  & -7.01\%  & 0.78\%  & 0.85\%  & - \tabularnewline
 & 5  & -0.46\%  & 0.29\%  & 0.00\%  & - \tabularnewline
 & 6  & 0.65\%  & 0.65\%  & 0.99\%  & - \tabularnewline
 & 7  & 0.00\%  & 0.00\%  & 0.00\%  & - \tabularnewline
\hline 
\multirow{5}{*}{10列车案例} & 1  & -1.54\%  & -0.38\%  & 0.27\%  & - \tabularnewline
 & 2  & -0.40\%  & -1.32\%  & -0.08\%  & - \tabularnewline
 & 3  & 0.45\%  & -1.14\%  & 0.54\%  & - \tabularnewline
 & 4  & 0.32\%  & 0.39\%  & 0.73\%  & - \tabularnewline
 & 5  & -0.43\%  & 0.89\%  & -0.07\%  & - \tabularnewline
\hline 
\end{tabular}
\end{table}

第二，共用分组的预分方式相比于仅仅通过通售分组或者“先到先服务”模式来说，能够产生更大的收益，尤其是在需求强度较高的时候。表\ref{tab:3-5}展示了不同客票销售规则的对比。在单列车案例中的情景5,6,7与10列车案例的情景4,5中，采用共用分组预分方式的优势更加明显。

\begin{table}[H]
\centering \bicaption[tab:3-5]{不同客票销售规则对收入的影响}{不同客票销售规则对收入的影响}{Table}{Comparison
of average revenue between different seat inventory controls} %
\begin{tabular}{ccccc}
\hline 
案例  & 情景  & $\gamma$  & 共用分组 - 通用分组  & 共用分组 - 先到先服务 \tabularnewline
\hline 
\multirow{7}{*}{单列车案例} & 1  & 0.26  & 37.53\%  & -0.48\% \tabularnewline
 & 2  & 0.51  & 23.87\%  & -5.21\% \tabularnewline
 & 3  & 1.03  & 6.98\%  & 12.51\% \tabularnewline
 & 4  & 1.55  & 4.89\%  & 18.13\% \tabularnewline
 & 5  & 2.07  & 3.22\%  & 20.06\% \tabularnewline
 & 6  & 2.58  & 1.20\%  & 16.06\% \tabularnewline
 & 7  & 3.09  & 3.59\%  & 17.54\% \tabularnewline
\hline 
\multirow{5}{*}{10列车案例} & 1  & 0.1  & 1.12\%  & -1.12\% \tabularnewline
 & 2  & 0.49  & -1.37\%  & -1.88\% \tabularnewline
 & 3  & 0.98  & -2.46\%  & -2.28\% \tabularnewline
 & 4  & 1.96  & 7.15\%  & 7.82\% \tabularnewline
 & 5  & 2.94  & 8.30\%  & 5.51\% \tabularnewline
\hline 
\end{tabular}
\end{table}


\section{模型讨论与拓展}

\subsection{向通售分组复用席位}

在本章提出的模型中，仅仅考虑了向通用分组复用席位的机制。事实上，复用机制的设置可以非常灵活。另一种常见的复用设置是把席位复用给通售分组。在本章的客票销售过程模型中，共用分组和通用分组机制通过状态变量$X_{t},Q_{t}$和状态转移函数$F(\cdot)$表达。如果要在此基础上进一步考虑通售分组机制，则应该加入新的状态变量和状态转移函数。

与共用分组的表达类似，对通售分组的表达同样需要分别描述其存量单位和可售产品。然而通售分组的表达会更加复杂。从存量单位状态上来看，其分组内的存量单位既不是和共用分组一样是整个席位加入与售出，也不是和通用分组一样是按照产品来管理，难以用聚合的状态变量来表示通用分组中的席位状态。所以，通售分组中的席位状态表达还需要回到使用存量单位的使用状态的表达。另外，在每出售一件产品之后，通售分组内可以支持的产品需要重新计算。也就是说，在引入通售分组后，$U_{t}$的确定也会变得更加复杂。

通售分组的状态转移与共用分组和通用分组相比，与席位分配规则有非常大的关联。席位分配规则决定了在通售分组中，如果两个席位都可以提供同一种产品，应该选择哪个席位。在本文的研究中，针对通售分组，主要考虑以下两种席位分配规则。第一种席位分配规则是按照席位编号规则。其基本原理是，假设在通售分组中要出售产品$j$，根据席位的编号从低到高逐一扫描，一旦找到一个席位可以出售产品$j$，则停止并从这个席位中售出一张产品$j$的车票。第二种席位分配规则是最大利用存量单位的可售席位规则。其原理是找到在可以出售此产品的席位中，找到并从对存量单位利用率最高的席位中出售产品。对存量单位利用率最高的可以由出售这种产品之后，此席位还能出售的种类来评价。如果一个席位出售当前产品后还能出售很多其它产品，说明出售此产品并没有最有效利用存量单位。基于这种规则可以更加有效利用存量单位。

\subsection{向后复用席位}

在某些不包含列车始发站的共用分组中，有一些席位一开始就可以进行复用。如例3-1中的共用分组2，由于其中产品的始发站都是B站或者C站。所以A-B区间的存量在预售期之前就可以以复用的方式进入通售或者通用分组。这样做有一个明显的优势，即A-B间出行的旅客不需要等待这个分组中出售车票后，A-B的车票被复用出来之后才能购票，而是一开始就能购买。

为了考虑向后复用的机制对售票结果的影响，在前文的求解过程当中，在仿真过程开始之前加入对向后复用机制。这样对求解过程的其它步骤并不会产生改变，同时向后复用机制带来的结果也可以有效的反馈到产品的边际收入中。

另外，在实践当中将所有可能的席位进行向后复用是有一定风险的：很多短途旅客会通过购买这种车票达到“买短乘长”的目的，对行车安全造成隐患（尤其是在席位紧张的季度）。所以，应该预先确定好向后复用席位的比例或者数量。

\subsection{向通用和通售分组中分配席位}

在本章的研究中，仅仅考虑了向共用分组中分配席位。然而在实际操作中，在票额预分中直接向通用和通售分组中分配席位也是可行的。为了考虑这一类问题，需要引入新的决策变量，即通用分组中的每个产品的销售上限和通售分组中的席位数量。本章提出的求解方法并不能直接用于求解这一类新的问题。但是在基于规则的启发式方法中引入的产品边际收入的概念还是可以用于评价一个分组，无论是共用分组、通售分组还是通用分组的重要指标。

\section{本章小节}

通过运用第二章提出的建模框架，本章通过马尔科夫链模型的状态变量和状态转移函数以解析形式表达票额预分的原理。由于问题的复杂性，本章设计了求解此问题的遗传算法，并通过基于规则的启发式方法生成初始解。最后通过仿真实验对比了票额预分与其它的控制策略，包括精确预分（分割式上限控制）和通售（“先到先服务”）的对售票收入的区别。相比与其它两种控制策略，在供不应求的市场环境下，采用共用分组控制能够显著提高售票收入。 
